#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;

class Solution {
public:
	int majorityElement(vector<int>& nums) {
		unordered_map<int,int> list;
		for (int i = 0; i < nums.size(); i++) {
			list[nums[i]]++;
		}
		int maxCount = -1,res=-1;
		for (auto element : list) {
			if (maxCount < element.second) {
				maxCount = element.second;
				res = element.first;
			}
		}
		return res;
	}

	int majorityElementOptimize(vector<int>& nums) {
		unordered_map<int, int> list;
		int maxCount = -1, res = -1;
		for (int num : nums) {
			list[num]++;
			if (list[num] > maxCount) {
				maxCount = list[num];
				res = num;
			}
		}
		return res;
	}


};

int main() {
	unordered_map<int, int> list;
	list.insert(pair<int,int>(1,1));
	list[1]++;
	list[1]++;
	list[1]++;
	list.insert(pair<int, int>(2, 1));
	list[2]++;
	Solution s;
	vector<int> arr = { 1,1,1,1,2,2,3,3,3,3,3,3,3 };
	int res = s.majorityElement(arr);
	cout << res << endl;
	return 0;
}